class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        def judge(s, p):
            length = len(s)
            count = 0
            for i in range(length):
                count += (s[i] == p[i])
            if count == length - 1:
                return True
            else:
                return False

        search_dict = {}
        search_list = [{beginWord}]
        while search_list[-1]:
            if endWord not in search_list[-1]:
                new_set = set()
                for item in search_list[-1]:
                    precedor = set()
                    for word in wordList:
                        if word not in search_dict and word not in search_list[-1]:
                            if judge(word, item):
                                precedor.add(word)
                                new_set.add(word)
                    search_dict[item] = precedor
                search_list.append(new_set)
            else:
                break
        if not search_list[-1]:
            return []
        for item in search_list[-1]:
            search_dict[item] = []
        return_list = []
        now_list = []
        def search(word):
            now_list.append(word)
            if word == endWord:
                return_list.append(now_list.copy())
            else:
                for item in search_dict[word]:
                    search(item)
            now_list.pop()
        search(beginWord)
        return return_list
